package com.fmm.hard;

public class PalindromicSubsequence {

    /**
     * @param s 字符串
     * @return 最长回文子序列的长度
     */
    public static int maxPalindromicSubLength(String s) {
        // 初始化动态规划矩阵
        int[][] dp = new int[s.length()][s.length()];
        // 斜对角循环填充值
        for (int loop = 0; loop < s.length(); loop++) {
            for (int i = loop; i < s.length(); i++) {
                // 注意：斜对角循环的时候，行列的下标的差值，和循环数是一致的
                // 比如 loop = 0 的时候，在本次循环中 i - j = 0
                // 比如 loop = 1 的时候，在本次循环中 i - j = 1
                // 规律就是 i - j = loop，也就是 j = i - loop
                if (loop == 0) {
                    dp[i][i] = 1;
                } else {
                    if (s.charAt(i) == s.charAt(i - loop)) {
                        dp[i][i - loop] = dp[i - 1][i - loop + 1] + 2;
                    } else {
                        dp[i][i - loop] = Math.max(dp[i - 1][i - loop], dp[i][i - loop + 1]);
                    }
                }
            }
        }
        return dp[s.length() - 1][0];
    }

    public static void main(String[] args) {
        System.out.println(maxPalindromicSubLength("bbbab"));
        System.out.println(maxPalindromicSubLength("cbbd"));
        System.out.println(maxPalindromicSubLength("c"));
    }
}
